1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.collect;
16
17 import static com.google.common.collect.BoundType.OPEN;
18 import static com.google.common.collect.testing.Helpers.mapEntry;
19
20 import com.google.common.annotations.GwtIncompatible;
21 import com.google.common.collect.testing.MapTestSuiteBuilder;
22 import com.google.common.collect.testing.SampleElements;
23 import com.google.common.collect.testing.TestMapGenerator;
24 import com.google.common.collect.testing.features.CollectionFeature;
25 import com.google.common.collect.testing.features.CollectionSize;
26 import com.google.common.collect.testing.features.MapFeature;
27
28 import junit.framework.Test;
29 import junit.framework.TestCase;
30 import junit.framework.TestSuite;
31
32 import java.util.List;
33 import java.util.Map;
34 import java.util.Map.Entry;
35 import java.util.NoSuchElementException;
36
37
38
39
40
41
42 @GwtIncompatible("NavigableMap")
43 public class TreeRangeMapTest extends TestCase {
44 public static Test suite() {
45 TestSuite suite = new TestSuite();
46 suite.addTestSuite(TreeRangeMapTest.class);
47 suite.addTest(MapTestSuiteBuilder.using(new TestMapGenerator<Range<Integer>, String>() {
48 @Override
49 public SampleElements<Entry<Range<Integer>, String>> samples() {
50 return new SampleElements<Entry<Range<Integer>, String>>(
51 mapEntry(Range.singleton(0), "banana"),
52 mapEntry(Range.closedOpen(3, 5), "frisbee"),
53 mapEntry(Range.atMost(-1), "fruitcake"),
54 mapEntry(Range.open(10, 15), "elephant"),
55 mapEntry(Range.closed(20, 22), "umbrella"));
56 }
57
58 @Override
59 public Map<Range<Integer>, String> create(Object... elements) {
60 RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
61 for (Object o : elements) {
62 @SuppressWarnings("unchecked")
63 Entry<Range<Integer>, String> entry = (Entry<Range<Integer>, String>) o;
64 rangeMap.put(entry.getKey(), entry.getValue());
65 }
66 return rangeMap.asMapOfRanges();
67 }
68
69 @SuppressWarnings("unchecked")
70 @Override
71 public Entry<Range<Integer>, String>[] createArray(int length) {
72 return new Entry[length];
73 }
74
75 @Override
76 public Iterable<Entry<Range<Integer>, String>> order(
77 List<Entry<Range<Integer>, String>> insertionOrder) {
78 return Range.RANGE_LEX_ORDERING.<Range<Integer>>onKeys()
79 .sortedCopy(insertionOrder);
80 }
81
82 @SuppressWarnings("unchecked")
83 @Override
84 public Range<Integer>[] createKeyArray(int length) {
85 return new Range[length];
86 }
87
88 @Override
89 public String[] createValueArray(int length) {
90 return new String[length];
91 }
92 })
93 .named("TreeRangeMap.asMapOfRanges")
94 .withFeatures(
95 CollectionSize.ANY,
96 MapFeature.SUPPORTS_REMOVE,
97 MapFeature.ALLOWS_ANY_NULL_QUERIES,
98 CollectionFeature.KNOWN_ORDER,
99 CollectionFeature.SUPPORTS_ITERATOR_REMOVE)
100 .createTestSuite());
101
102 suite.addTest(MapTestSuiteBuilder.using(new TestMapGenerator<Range<Integer>, String>() {
103 @Override
104 public SampleElements<Entry<Range<Integer>, String>> samples() {
105 return new SampleElements<Entry<Range<Integer>, String>>(
106 mapEntry(Range.singleton(0), "banana"),
107 mapEntry(Range.closedOpen(3, 5), "frisbee"),
108 mapEntry(Range.atMost(-1), "fruitcake"),
109 mapEntry(Range.open(10, 15), "elephant"),
110 mapEntry(Range.closed(20, 22), "umbrella"));
111 }
112
113 @Override
114 public Map<Range<Integer>, String> create(Object... elements) {
115 RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
116 for (Object o : elements) {
117 @SuppressWarnings("unchecked")
118 Entry<Range<Integer>, String> entry = (Entry<Range<Integer>, String>) o;
119 rangeMap.put(entry.getKey(), entry.getValue());
120 }
121 return rangeMap.subRangeMap(Range.atMost(22)).asMapOfRanges();
122 }
123
124 @SuppressWarnings("unchecked")
125 @Override
126 public Entry<Range<Integer>, String>[] createArray(int length) {
127 return new Entry[length];
128 }
129
130 @Override
131 public Iterable<Entry<Range<Integer>, String>> order(
132 List<Entry<Range<Integer>, String>> insertionOrder) {
133 return Range.RANGE_LEX_ORDERING.<Range<Integer>>onKeys()
134 .sortedCopy(insertionOrder);
135 }
136
137 @SuppressWarnings("unchecked")
138 @Override
139 public Range<Integer>[] createKeyArray(int length) {
140 return new Range[length];
141 }
142
143 @Override
144 public String[] createValueArray(int length) {
145 return new String[length];
146 }
147 })
148 .named("TreeRangeMap.subRangeMap.asMapOfRanges")
149 .withFeatures(
150 CollectionSize.ANY,
151 MapFeature.SUPPORTS_REMOVE,
152 MapFeature.ALLOWS_ANY_NULL_QUERIES,
153 CollectionFeature.KNOWN_ORDER)
154 .createTestSuite());
155 return suite;
156 }
157
158 private static final ImmutableList<Range<Integer>> RANGES;
159 private static final int MIN_BOUND = -2;
160 private static final int MAX_BOUND = 2;
161 static {
162 ImmutableList.Builder<Range<Integer>> builder = ImmutableList.builder();
163
164 builder.add(Range.<Integer>all());
165
166
167 for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
168 for (BoundType type : BoundType.values()) {
169 builder.add(Range.upTo(i, type));
170 builder.add(Range.downTo(i, type));
171 }
172 }
173
174
175 for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
176 for (int j = i; j <= MAX_BOUND; j++) {
177 for (BoundType lowerType : BoundType.values()) {
178 for (BoundType upperType : BoundType.values()) {
179 if (i == j & lowerType == OPEN & upperType == OPEN) {
180 continue;
181 }
182 builder.add(Range.range(i, lowerType, j, upperType));
183 }
184 }
185 }
186 }
187 RANGES = builder.build();
188 }
189
190 public void testSpanSingleRange() {
191 for (Range<Integer> range : RANGES) {
192 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
193 rangeMap.put(range, 1);
194
195 try {
196 assertEquals(range, rangeMap.span());
197 assertFalse(range.isEmpty());
198 } catch (NoSuchElementException e) {
199 assertTrue(range.isEmpty());
200 }
201 }
202 }
203
204 public void testSpanTwoRanges() {
205 for (Range<Integer> range1 : RANGES) {
206 for (Range<Integer> range2 : RANGES) {
207 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
208 rangeMap.put(range1, 1);
209 rangeMap.put(range2, 2);
210
211 Range<Integer> expected;
212 if (range1.isEmpty()) {
213 if (range2.isEmpty()) {
214 expected = null;
215 } else {
216 expected = range2;
217 }
218 } else {
219 if (range2.isEmpty()) {
220 expected = range1;
221 } else {
222 expected = range1.span(range2);
223 }
224 }
225
226 try {
227 assertEquals(expected, rangeMap.span());
228 assertNotNull(expected);
229 } catch (NoSuchElementException e) {
230 assertNull(expected);
231 }
232 }
233 }
234 }
235
236 public void testAllRangesAlone() {
237 for (Range<Integer> range : RANGES) {
238 Map<Integer, Integer> model = Maps.newHashMap();
239 putModel(model, range, 1);
240 RangeMap<Integer, Integer> test = TreeRangeMap.create();
241 test.put(range, 1);
242 verify(model, test);
243 }
244 }
245
246 public void testAllRangePairs() {
247 for (Range<Integer> range1 : RANGES) {
248 for (Range<Integer> range2 : RANGES) {
249 Map<Integer, Integer> model = Maps.newHashMap();
250 putModel(model, range1, 1);
251 putModel(model, range2, 2);
252 RangeMap<Integer, Integer> test = TreeRangeMap.create();
253 test.put(range1, 1);
254 test.put(range2, 2);
255 verify(model, test);
256 }
257 }
258 }
259
260 public void testAllRangeTriples() {
261 for (Range<Integer> range1 : RANGES) {
262 for (Range<Integer> range2 : RANGES) {
263 for (Range<Integer> range3 : RANGES) {
264 Map<Integer, Integer> model = Maps.newHashMap();
265 putModel(model, range1, 1);
266 putModel(model, range2, 2);
267 putModel(model, range3, 3);
268 RangeMap<Integer, Integer> test = TreeRangeMap.create();
269 test.put(range1, 1);
270 test.put(range2, 2);
271 test.put(range3, 3);
272 verify(model, test);
273 }
274 }
275 }
276 }
277
278 public void testPutAll() {
279 for (Range<Integer> range1 : RANGES) {
280 for (Range<Integer> range2 : RANGES) {
281 for (Range<Integer> range3 : RANGES) {
282 Map<Integer, Integer> model = Maps.newHashMap();
283 putModel(model, range1, 1);
284 putModel(model, range2, 2);
285 putModel(model, range3, 3);
286 RangeMap<Integer, Integer> test = TreeRangeMap.create();
287 RangeMap<Integer, Integer> test2 = TreeRangeMap.create();
288
289 test.put(range1, 1);
290 test2.put(range2, 2);
291 test2.put(range3, 3);
292 test.putAll(test2);
293 verify(model, test);
294 }
295 }
296 }
297 }
298
299 public void testPutAndRemove() {
300 for (Range<Integer> rangeToPut : RANGES) {
301 for (Range<Integer> rangeToRemove : RANGES) {
302 Map<Integer, Integer> model = Maps.newHashMap();
303 putModel(model, rangeToPut, 1);
304 removeModel(model, rangeToRemove);
305 RangeMap<Integer, Integer> test = TreeRangeMap.create();
306 test.put(rangeToPut, 1);
307 test.remove(rangeToRemove);
308 verify(model, test);
309 }
310 }
311 }
312
313 public void testPutTwoAndRemove() {
314 for (Range<Integer> rangeToPut1 : RANGES) {
315 for (Range<Integer> rangeToPut2 : RANGES) {
316 for (Range<Integer> rangeToRemove : RANGES) {
317 Map<Integer, Integer> model = Maps.newHashMap();
318 putModel(model, rangeToPut1, 1);
319 putModel(model, rangeToPut2, 2);
320 removeModel(model, rangeToRemove);
321 RangeMap<Integer, Integer> test = TreeRangeMap.create();
322 test.put(rangeToPut1, 1);
323 test.put(rangeToPut2, 2);
324 test.remove(rangeToRemove);
325 verify(model, test);
326 }
327 }
328 }
329 }
330
331 public void testSubRangeMapExhaustive() {
332 for (Range<Integer> range1 : RANGES) {
333 for (Range<Integer> range2 : RANGES) {
334 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
335 rangeMap.put(range1, 1);
336 rangeMap.put(range2, 2);
337
338 for (Range<Integer> subRange : RANGES) {
339 RangeMap<Integer, Integer> expected = TreeRangeMap.create();
340 for (Map.Entry<Range<Integer>, Integer> entry : rangeMap.asMapOfRanges().entrySet()) {
341 if (entry.getKey().isConnected(subRange)) {
342 expected.put(entry.getKey().intersection(subRange), entry.getValue());
343 }
344 }
345 RangeMap<Integer, Integer> subRangeMap = rangeMap.subRangeMap(subRange);
346 assertEquals(expected, subRangeMap);
347 assertEquals(expected.asMapOfRanges(), subRangeMap.asMapOfRanges());
348
349 if (!expected.asMapOfRanges().isEmpty()) {
350 assertEquals(expected.span(), subRangeMap.span());
351 }
352
353 for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
354 assertEquals(expected.get(i), subRangeMap.get(i));
355 }
356
357 for (Range<Integer> query : RANGES) {
358 assertEquals(
359 expected.asMapOfRanges().get(query),
360 subRangeMap.asMapOfRanges().get(query));
361 }
362 }
363 }
364 }
365 }
366
367 public void testSubSubRangeMap() {
368 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
369 rangeMap.put(Range.open(3, 7), 1);
370 rangeMap.put(Range.closed(9, 10), 2);
371 rangeMap.put(Range.closed(12, 16), 3);
372 RangeMap<Integer, Integer> sub1 = rangeMap.subRangeMap(Range.closed(5, 11));
373 assertEquals(ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.closed(9, 10), 2),
374 sub1.asMapOfRanges());
375 RangeMap<Integer, Integer> sub2 = sub1.subRangeMap(Range.open(6, 15));
376 assertEquals(ImmutableMap.of(Range.open(6, 7), 1, Range.closed(9, 10), 2),
377 sub2.asMapOfRanges());
378 }
379
380 public void testSubRangeMapPut() {
381 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
382 rangeMap.put(Range.open(3, 7), 1);
383 rangeMap.put(Range.closed(9, 10), 2);
384 rangeMap.put(Range.closed(12, 16), 3);
385 RangeMap<Integer, Integer> sub = rangeMap.subRangeMap(Range.closed(5, 11));
386 assertEquals(ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.closed(9, 10), 2),
387 sub.asMapOfRanges());
388 sub.put(Range.closed(7, 9), 4);
389 assertEquals(
390 ImmutableMap.of(
391 Range.closedOpen(5, 7), 1, Range.closed(7, 9), 4, Range.openClosed(9, 10), 2),
392 sub.asMapOfRanges());
393 assertEquals(
394 ImmutableMap.of(Range.open(3, 7), 1, Range.closed(7, 9), 4, Range.openClosed(9, 10), 2,
395 Range.closed(12, 16), 3),
396 rangeMap.asMapOfRanges());
397
398 try {
399 sub.put(Range.open(9, 12), 5);
400 fail("Expected IllegalArgumentException");
401 } catch (IllegalArgumentException expected) {
402 }
403
404 sub = sub.subRangeMap(Range.closedOpen(5, 5));
405 sub.put(Range.closedOpen(5, 5), 6);
406 assertEquals(
407 ImmutableMap.of(Range.open(3, 7), 1, Range.closed(7, 9), 4, Range.openClosed(9, 10), 2,
408 Range.closed(12, 16), 3),
409 rangeMap.asMapOfRanges());
410 }
411
412 public void testSubRangeMapRemove() {
413 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
414 rangeMap.put(Range.open(3, 7), 1);
415 rangeMap.put(Range.closed(9, 10), 2);
416 rangeMap.put(Range.closed(12, 16), 3);
417 RangeMap<Integer, Integer> sub = rangeMap.subRangeMap(Range.closed(5, 11));
418 assertEquals(ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.closed(9, 10), 2),
419 sub.asMapOfRanges());
420 sub.remove(Range.closed(7, 9));
421 assertEquals(
422 ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.openClosed(9, 10), 2),
423 sub.asMapOfRanges());
424 assertEquals(
425 ImmutableMap.of(Range.open(3, 7), 1, Range.openClosed(9, 10), 2, Range.closed(12, 16), 3),
426 rangeMap.asMapOfRanges());
427
428 sub.remove(Range.closed(3, 9));
429 assertEquals(
430 ImmutableMap.of(Range.openClosed(9, 10), 2),
431 sub.asMapOfRanges());
432 assertEquals(
433 ImmutableMap.of(Range.open(3, 5), 1, Range.openClosed(9, 10), 2, Range.closed(12, 16), 3),
434 rangeMap.asMapOfRanges());
435 }
436
437 public void testSubRangeMapClear() {
438 RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
439 rangeMap.put(Range.open(3, 7), 1);
440 rangeMap.put(Range.closed(9, 10), 2);
441 rangeMap.put(Range.closed(12, 16), 3);
442 RangeMap<Integer, Integer> sub = rangeMap.subRangeMap(Range.closed(5, 11));
443 sub.clear();
444 assertEquals(
445 ImmutableMap.of(Range.open(3, 5), 1, Range.closed(12, 16), 3),
446 rangeMap.asMapOfRanges());
447 }
448
449 private void verify(Map<Integer, Integer> model, RangeMap<Integer, Integer> test) {
450 for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
451 assertEquals(model.get(i), test.get(i));
452
453 Map.Entry<Range<Integer>, Integer> entry = test.getEntry(i);
454 assertEquals(model.containsKey(i), entry != null);
455 if (entry != null) {
456 assertTrue(test.asMapOfRanges().entrySet().contains(entry));
457 }
458 }
459 for (Range<Integer> range : test.asMapOfRanges().keySet()) {
460 assertFalse(range.isEmpty());
461 }
462 }
463
464 private void putModel(Map<Integer, Integer> model, Range<Integer> range, int value) {
465 for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
466 if (range.contains(i)) {
467 model.put(i, value);
468 }
469 }
470 }
471
472 private void removeModel(Map<Integer, Integer> model, Range<Integer> range) {
473 for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
474 if (range.contains(i)) {
475 model.remove(i);
476 }
477 }
478 }
479 }